package com.bwt.recursion;

public class Queue8 {
	// 定义一个max 表示共有多少个皇后
	int max = 8;
	// 定义一个数组 , 表示皇后放置的结果
	int[] arr = new int[max];
	static int count = 0;
	static int judgeCount = 0;
	public static void main(String[] args) {
		Queue8 queue8 = new Queue8();
		queue8.check(0);
		System.out.println("一共有"+count+"种算法"); //92
		System.out.println("一共判断冲突的次数"+judgeCount+"次"); //15720
	}

	//放置第n个皇后
	//特别注意: check 是 每一次递归都有一个for循环, 因此就会有回溯
	private void check(int n) {
		if (n == max) {  // n==8 ,n是从零开始, 其实前8个皇后已经放好
			print();
			return;
		}

		//依次放入皇后
		for (int i = 0; i < max; i++) {
			//先把当前这个皇后n , 放到当前该行的第1列
			arr[n] = i;
			//判断当前放置的第n个皇后到第i列时, 是否冲突
			//如果冲突, 则不会进入if判断调用递归 , 而是继续fori循环,将n放在第i个位置
			if (judge(n)) { //不冲突
				//接着放n+1个皇后, 即开始递归
				check(n+1);
			}
		}
 	}

	// int n 表示第几个皇后
	private boolean judge( int n) {
		judgeCount++;
		for (int i = 0; i < n; i++) {
			//说明
			//1. arr[i] == arr[n] 判断前面第n个皇后是否和前面的n-1个皇后在同一列
			//2.  Math.abs(n - i) == Math.abs(arr[n] - arr[i]) 表示判断第n个皇后和第i个皇后是否在同一斜线上
			//假如n = (1,1) 第二行第二列, i = (0,0) 放置在第1行 第1列   Math.abs(1 - 0) =  Math.abs(1 - 0)
			if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
				return false;
			}
		}
		return true;
	}

	public void print() {
		count++;
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
}
